//94. 二叉树的中序遍历
//给定一个二叉树的根节点 root ，返回它的 中序 遍历。

#include <stdlib.h>
#include <stdio.h>
#include "tree_node.h"

//将数据收集到缓冲区中
static void collectNum(int num, int *index, int **buf, int *bufLen)
{
    if (*index == *bufLen) //索引超过缓冲区大小
    {
        int newBufLen = (*bufLen) * 3 * 2;
        *buf = realloc(*buf, sizeof(int) * newBufLen); //扩容
        *bufLen = newBufLen;                           //更新缓冲区大小
    }
    (*buf)[*index] = num;  //放到数组中
    *index = (*index + 1); //游标移动
}

//中序遍历
static void doInorderTraversal(struct TreeNode *root, int *index, int **buf, int *bufLen)
{
    if (root == NULL)
    {
        return;
    }
    //遍历左子树
    doInorderTraversal(root->left, index, buf, bufLen);
    //收集根节点的数据
    collectNum(root->val, index, buf, bufLen);
    //遍历右子树
    doInorderTraversal(root->right, index, buf, bufLen);
}

static int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    int bufLen = 8;                                  //缓冲区初始大小
    int index = 0;                                   //数组索引 从0开始
    int *buf = (int *)calloc(bufLen, sizeof(int));   //分配缓冲区
    doInorderTraversal(root, &index, &buf, &bufLen); //遍历二叉树
    *returnSize = index;
    buf = realloc(buf, sizeof(int) * index); //调整缓冲区大小
    return buf;
}

int main12()
{
    struct TreeNode node1;
    struct TreeNode node2;
    struct TreeNode node3;
    node1.val = 1;
    node1.left = NULL;
    node1.right = &node2;

    node2.val = 2;
    node2.left = &node3;
    node2.right = NULL;

    node3.val = 3;
    node3.left = NULL;
    node3.right = NULL;
    int size = 0;
    int *buf = inorderTraversal(&node1, &size);

    for (int i = 0; i < size; i++)
    {
        printf("%d,", buf[i]);
    }
}